package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * 注意：给定 n 是一个正整数。
 * https://leetcode-cn.com/problems/climbing-stairs/
 * @version 1.0
 * @date 2021/11/10 15:09
 */
public class climbStairs {
    public static void main(String[] args) {
        System.out.println(climbStairs(45));
    }

    // 这种递归解法，没有利用到计算过得值，比如n = 10时，需要计算 climbStairs(9), climbStairs(8)。
    // 计算climbStairs(9)时，又要计算climbStairs(8)
    static int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    // Dynamic Programming：定义变量（变量具体在题目中代表什么），找到变量之间的关系，找到初始值。
    static int climbStairs1(int n) {
        // climbStairs(n - 1) + climbStairs(n - 2);
        // big 表示 climbStairs(n - 1)，small 表示 climbStairs(n - 2)
        int small = 1;
        int big = 2;
        if (n == 1) return small;
        if (n == 2) return big;
        for (int i = 3; i < n; i++) {
            if (small < big) small = small + big;
            else big = small + big;
        }
        return small + big;
    }
}
